use std::{
    borrow::Borrow,
    hash::Hasher,
    mem::{self, MaybeUninit},
};
use std::{collections::HashMap, hash::Hash, ptr};

struct KeyRef<K> {
    k: *const K,
}

impl<K: Hash> Hash for KeyRef<K> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        unsafe { (*self.k).hash(state) }
    }
}

impl<K: PartialEq> PartialEq for KeyRef<K> {
    fn eq(&self, other: &KeyRef<K>) -> bool {
        unsafe { (*self.k).eq(&*other.k) }
    }
}

impl<K: Eq> Eq for KeyRef<K> {}

impl<K> Borrow<K> for KeyRef<K> {
    fn borrow(&self) -> &K {
        unsafe { &*self.k }
    }
}

struct LruEntry<K, V> {
    next: *mut LruEntry<K, V>,
    prev: *mut LruEntry<K, V>,
    key: MaybeUninit<K>,
    value: MaybeUninit<V>,
}

impl<K, V> LruEntry<K, V> {
    fn new(k: K, v: V) -> Self {
        Self {
            key: MaybeUninit::new(k),
            value: MaybeUninit::new(v),
            next: ptr::null_mut(),
            prev: ptr::null_mut(),
        }
    }

    fn new_sigil() -> Self {
        Self {
            key: MaybeUninit::uninit(),
            value: MaybeUninit::uninit(),
            next: ptr::null_mut(),
            prev: ptr::null_mut(),
        }
    }
}

pub struct LruCache<K, V> {
    map: HashMap<KeyRef<K>, Box<LruEntry<K, V>>>,
    max_size: usize,
    head: *mut LruEntry<K, V>,
    tail: *mut LruEntry<K, V>,
}

impl<K: Hash + Eq, V> LruCache<K, V> {
    pub fn new(capacity: usize) -> Self {
        let cache = LruCache {
            map: HashMap::new(),
            max_size: capacity,
            head: Box::into_raw(Box::new(LruEntry::new_sigil())),
            tail: Box::into_raw(Box::new(LruEntry::new_sigil())),
        };

        unsafe {
            (*cache.head).next = cache.tail;
            (*cache.tail).prev = cache.head;
        }

        cache
    }

    pub fn cap(&self) -> usize {
        self.max_size
    }

    pub fn len(&self) -> usize {
        self.map.len()
    }

    pub fn put(&mut self, k: K, mut v: V) -> Option<V> {
        let node_ptr = self.map.get_mut(&KeyRef { k: &k }).map(|node| {
            let node_ptr: *mut LruEntry<_, _> = &mut **node;
            node_ptr
        });
        match node_ptr {
            Some(node_ptr) => {
                unsafe { mem::swap(&mut v, &mut (*(*node_ptr).value.as_mut_ptr()) as &mut V) };
                self.detach(node_ptr);
                self.attach(node_ptr);
                Some(v)
            }
            None => {
                if self.cap() == 0 {
                    return None;
                }

                let mut node = if self.len() == self.cap() {
                    let old_key = KeyRef {
                        k: unsafe { &(*(*(*self.tail).prev).key.as_ptr()) },
                    };
                    let mut old_node = self.map.remove(&old_key).unwrap();
                    unsafe {
                        ptr::drop_in_place(old_node.key.as_mut_ptr());
                        ptr::drop_in_place(old_node.value.as_mut_ptr());
                    }
                    old_node.key = MaybeUninit::new(k);
                    old_node.value = MaybeUninit::new(v);

                    let node_ptr: *mut _ = &mut *old_node;
                    self.detach(node_ptr);

                    old_node
                } else {
                    Box::new(LruEntry::new(k, v))
                };

                let node_ptr: *mut _ = &mut *node;
                self.attach(node_ptr);

                let keyref = unsafe { (*node_ptr).key.as_mut_ptr() };

                self.map.insert(KeyRef { k: keyref }, node);
                None
            }
        }
    }

    pub fn get<'a>(&'a mut self, k: &K) -> Option<&'a V> {
        if let Some(node) = self.map.get_mut(&KeyRef { k }) {
            let node_ptr: *mut LruEntry<_, _> = &mut (**node);

            self.detach(node_ptr);
            self.attach(node_ptr);
            Some(unsafe { &(*(*node_ptr).value.as_ptr()) as &V })
        } else {
            None
        }
    }

    pub fn get_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> {
        if let Some(node) = self.map.get_mut(&KeyRef { k }) {
            let node_ptr: *mut LruEntry<_, _> = &mut (**node);

            self.detach(node_ptr);
            self.attach(node_ptr);
            Some(unsafe { &mut (*(*node_ptr).value.as_mut_ptr()) as &mut V })
        } else {
            None
        }
    }

    fn detach(&mut self, node: *mut LruEntry<K, V>) {
        unsafe {
            (*(*node).prev).next = (*node).next;
            (*(*node).next).prev = (*node).prev;
        }
    }

    fn attach(&mut self, node: *mut LruEntry<K, V>) {
        unsafe {
            (*node).next = (*self.head).next;
            (*node).prev = self.head;
            (*self.head).next = node;
            (*(*node).next).prev = node;
        }
    }
}

impl<K, V> Drop for LruCache<K, V> {
    fn drop(&mut self) {
        self.map.values_mut().for_each(|e| unsafe {
            ptr::drop_in_place(e.key.as_mut_ptr());
            ptr::drop_in_place(e.value.as_mut_ptr());
        });
        // We rebox the head/tail, and because these are maybe-uninit
        // they do not have the absent k/v dropped.
        unsafe {
            let _head = *Box::from_raw(self.head);
            let _tail = *Box::from_raw(self.tail);
        }
    }
}
